use std::u32;

pub fn dp_rec_mc(amount: u32) -> u32 {
    let caches = [1, 2, 5, 10, 20, 30, 50, 100];
    // 递归性能很慢，用切片来优化
    //rec_mc(amount, &caches)
    let mut cache = vec![0u32; (amount + 1u32) as usize];
    //rec_mc_with_slice(amount, &caches, &mut cache)
    dp_mc(&caches, amount, &mut cache)
}

/// dp 三要素：重叠子问题，最优子结构，状态转移方程，且保证无后效性，从小到大递推
/// recurcive 三要素：基本情况，往基本情况靠近，调用自身，从大到小递归，从小到大回溯  
/// recurcive 三要素：基本情况：amount包含在caches中返回1；每找一个零，问题朝着边界靠近；调用自身。
/// 贪婪算法 每次都找最接近的当前最优解 但最终结果不一定是全局最优
/// f(amount) = f(amount') + 1
pub fn rec_mc(amount: u32, caches: &[u32]) -> u32 {
    let mut min_caches = amount;
    if caches.contains(&amount) {
        return 1;
    } else {
        for c in caches
            .iter()
            .filter(|&&x| x <= amount)
            .collect::<Vec<&u32>>()
        {
            let num_caches = 1 + rec_mc(amount - c, &caches);
            if num_caches < min_caches {
                min_caches = num_caches;
            }
        }
    }
    min_caches
}

pub fn rec_mc_with_slice(amount: u32, caches: &[u32], min_caches: &mut Vec<u32>) -> u32 {
    let mut min_cache = amount;
    if caches.contains(&amount) {
        min_caches[amount as usize] = 1;
        return 1;
    } else if min_caches[amount as usize] > 0 {
        return min_caches[amount as usize];
    } else {
        for c in caches
            .iter()
            .filter(|&&x| x <= amount)
            .collect::<Vec<&u32>>()
        {
            let num_cache = 1 + rec_mc_with_slice(amount - c, &caches, min_caches);
            if num_cache < min_cache {
                min_cache = num_cache;
                min_caches[amount as usize] = min_cache;
            }
        }
    }
    min_cache
}

fn dp_mc(caches: &[u32], amount: u32, min_caches: &mut Vec<u32>) -> u32 {
    for a in 1..=amount {
        let mut min_cache_num = a;
        for c in caches.iter().filter(|&&x| x <= a).collect::<Vec<&u32>>() {
            let index = (a - c) as usize;
            let cache_num = 1 + min_caches[index];
            if cache_num < min_cache_num {
                min_cache_num = cache_num;
            }
        }
        min_caches[a as usize] = min_cache_num;
    }
    min_caches[amount as usize]
}
